Skip to main content

删除链表的倒数第 k 个结点

021. 删除链表的倒数第 k 个结点

给定一个链表，删除链表的倒数第 k 个结点，并且返回链表的头结点。

示例 1:

输入：head = [1,2,3,4,5], k = 2
输出：[1,2,3,5]

示例 2:

输入：head = [1], k = 1
输出：[]

示例 3:

输入：head = [1,2], k = 1
输出：[1]

代码

思路：快慢指针

创建虚拟头节点 dummyNode
声明快慢指针
- slow
- fast
根据 k 递减通过快指针截取链表后部分
- while 遍历
  - 终止条件 while(k-- <0)
同时遍历快慢指针，当快指针结束，则慢指针为最终倒数位置
- while 循环原链表
  - 终止条件 while(fast && fast.next)
  - slow 为原链表对应的节点上节点
    while (fast && fast.next) { fast = fast.next slow = slow.next }
删除节点：让上节点的等于下下节点
返回删除后的链表的头节点

const head = {
  val: 1,
  next: {
    val: 2,
    next: {
      val: 3,
      next: {
        val: 4,
        next: {
          val: 5,
          next: undefined
        }
      }
    }
  }
}

const k = 2

class ListNode{
  constructor(val,next){
    this.val = val;
    this.next = next;
  }
}

var removeNthFromEnd = function(head, k) {
  let dummyNode = new ListNode(-1,head);

  // 声明快慢指针
  let fast = dummyNode
  let slow = dummyNode

  // 获取正序的目标
  while (k-- > 0) {
    fast = fast.next
  }

  // 根据正序获取反序的目标
  while(fast && fast.next){
    fast = fast.next
    slow = slow.next
  }

  // 替换节点
  slow.next = slow.next.next

  return dummyNode.next
};

console.log(removeNthFromEnd(head, k))

021. 删除链表的倒数第 k 个结点
代码